MOD = 1000000007  # 定义一个常量MOD，用于对斐波那契数进行取模操作
  
def fib_helper(k, memo):    
    """  
    k (int): 需要计算的斐波那契数的索引（位置）。  
    memo (dict): 用于缓存已计算的斐波那契数的字典。  
    """  
    # 如果memo中已经存储了第k个斐波那契数，则直接返回  
    if k in memo:    
        return memo[k]    
      
    # 递归地计算第k个斐波那契数，并存储在memo中以便后续使用  
    memo[k] = (fib_helper(k - 1, memo) + fib_helper(k - 2, memo)) % MOD    
    
    return memo[k]    
    

def fibonacci(n: int) -> int:    
    # 初始化memo字典，其中预存了斐波那契数列的前两个数：0和1  
    memo = {0: 0, 1: 1}    
    
    return fib_helper(n, memo)    
    
# 测试代码   
print(fibonacci(2))  
print(fibonacci(5))
print(fibonacci(100))
print(fibonacci(200))
